<html>
 <head>
  <meta charset="UTF-8">
 </head>
 <body>
  <h1 data-lake-id="cOnYi" id="cOnYi"><span data-lake-id="u685782c7" id="u685782c7">典型回答</span></h1>
  <p data-lake-id="u6b1760f2" id="u6b1760f2"><span data-lake-id="u5e00b257" id="u5e00b257">树的遍历方式多种多样，除了有前，中，后序三种遍历方式，还有层次遍历等。同时每种方式一般可以通过递归的方式实现。但是在面试的过程中，面试官往往会让应聘者通过栈或者队列实现。</span></p>
  <h2 data-lake-id="RtvJZ" id="RtvJZ"><span data-lake-id="ub6b6266d" id="ub6b6266d">前序遍历</span></h2>
  <p data-lake-id="u2e5f0105" id="u2e5f0105"><span data-lake-id="u5a88dd84" id="u5a88dd84">前序遍历是指：先遍历根节点，再遍历左节点，最后遍历右节点</span></p>
  <pre lang="java"><code>
List&lt;Integer&gt; output = new ArrayList&lt;&gt;(100);
private void preOrder(TreeNode node) {
   if(node == null) return;
   output.add(node.val);
   preOrder(node.left);
   preOrder(node.right);
}
</code></pre>
  <p data-lake-id="uc4029761" id="uc4029761"><span data-lake-id="u2387aea1" id="u2387aea1">前序遍历可以通过栈来完成，我们可以先让根节点的右节点入栈和左节点入栈。然后再让其出栈，这样我们就会先获取到左节点，再获取到右节点了。依次循环即可</span></p>
  <pre lang="java"><code>
public List&lt;Integer&gt; preorderWithStack(TreeNode root) {
    List&lt;Integer&gt; output = new ArrayList&lt;&gt;();
    Stack&lt;TreeNode&gt; stack = new Stack&lt;&gt;();
    if(root == null) return output;
    stack.push(root);
    while(!stack.isEmpty()) {
        TreeNode node = stack.pop();
        output.add(node.val);
        // 先放右再放左
        if(node.right != null) stack.push(node.right);
        if(node.left != null) stack.push(node.left);
    }
    return output;
}
</code></pre>
  <h2 data-lake-id="Wv3Ew" id="Wv3Ew"><span data-lake-id="ua54ffc2d" id="ua54ffc2d">中序遍历</span></h2>
  <p data-lake-id="u06e81d27" id="u06e81d27"><span data-lake-id="ua59fc8f3" id="ua59fc8f3">中序遍历是指：先遍历左节点，再遍历根节点，最后遍历右节点</span></p>
  <pre lang="java"><code>
List&lt;Integer&gt; ints = new ArrayList&lt;&gt;();
private void inOrder(TreeNode node) {
    if(node == null) return;
    inOrder(node.left);
    ints.add(node.val);
    inOrder(node.right);
}
</code></pre>
  <p data-lake-id="uc7b384d5" id="uc7b384d5"><span data-lake-id="u4240e447" id="u4240e447">中序遍历时，一定要先遍历到最左边的节点，所以中序遍历不同于前序遍历那种直接根节点入栈出栈即可。</span></p>
  <p data-lake-id="u705e1d58" id="u705e1d58"><span data-lake-id="u50c719ee" id="u50c719ee">中序遍历的时候，一定要先依次把左节点放入栈中，然后出栈。进行左，中，右的遍历。遇到右节点的时候，依然需要把右节点作为根节点，重新循环上述步骤</span></p>
  <pre lang="java"><code>
public List&lt;Integer&gt; inorderTraversal(TreeNode root) {
    List&lt;Integer&gt; list = new ArrayList&lt;&gt;();
    Stack&lt;TreeNode&gt; stack = new Stack&lt;&gt;();
    TreeNode node = root;
    while(node != null || !stack.isEmpty()) {
        while(node != null) {
            stack.push(node);
            node = node.left;
        }
        TreeNode temp = stack.pop();
        list.add(temp.val);
        // 后续遍历该右节点
        node = temp.right;
    }
    return list;
}
</code></pre>
  <h2 data-lake-id="dG0s2" id="dG0s2"><span data-lake-id="ud36fdd4b" id="ud36fdd4b">后序遍历</span></h2>
  <p data-lake-id="ubfda0773" id="ubfda0773"><span data-lake-id="u2ec48672" id="u2ec48672">后序遍历是指：先遍历左节点，再遍历右节点，最后遍历根节点</span></p>
  <pre lang="java"><code>
List&lt;Integer&gt; ints = new ArrayList&lt;&gt;();
private void postOrder(TreeNode node) {
    if(node == null) return;
    postOrder(node.left);
	postOrder(node.right);
    ints.add(node.val);
}
</code></pre>
  <p data-lake-id="uff1c9fb7" id="uff1c9fb7"><span data-lake-id="u6bc3856c" id="u6bc3856c">不同于前序遍历和中序遍历，后续遍历需要两个栈才可以完成，这是因为根节点需要放置到最后面的原因。我们需要一个栈记录遍历的顺序，同时需要另一个栈来记录遍历的结果，如下所示：</span></p>
  <pre lang="java"><code>
public List&lt;Integer&gt; postorderTraversal(TreeNode root) {
    List&lt;Integer&gt; ints = new ArrayList&lt;&gt;();
    Stack&lt;TreeNode&gt; stack1 = new Stack&lt;&gt;();
    Stack&lt;TreeNode&gt; stack2 = new Stack&lt;&gt;();
    if(root == null) return ints;
    stack1.push(root);
    while(!stack1.isEmpty()) {
       TreeNode node = stack1.pop();
       stack2.push(node);
       if(node.left != null) stack1.push(node.left);
       if(node.right != null) stack1.push(node.right);
    } 
    while(!stack2.isEmpty()) ints.add(stack2.pop().val);
    return ints;
}
</code></pre>
  <h2 data-lake-id="xUY5g" id="xUY5g"><span data-lake-id="u3ded70f2" id="u3ded70f2">层次遍历</span></h2>
  <p data-lake-id="u2210e941" id="u2210e941"><span data-lake-id="ue1e0fe8d" id="ue1e0fe8d">层次遍历是指按照树的每一层进行遍历，譬如先遍历根节点，再遍历第一层，第二层，直到每一层都遍历完成。这个时候我们就需要用到先进先出的特性，这个只能用队列实现，如下代码所示：</span></p>
  <pre lang="java"><code>
public List&lt;List&lt;Integer&gt;&gt; levelOrder(TreeNode root) {
    List&lt;List&lt;Integer&gt;&gt; list = new ArrayList&lt;&gt;();
    Queue&lt;TreeNode&gt; queue = new LinkedList&lt;&gt;();
    if(root != null) queue.offer(root);
    while(!queue.isEmpty()) {
        int n = queue.size();
        List&lt;Integer&gt; ints = new ArrayList&lt;&gt;();
        for(int i = 0; i &lt; n; i ++) {
            TreeNode node = queue.poll();
            ints.add(node.val);
            if(node.left != null) queue.offer(node.left);
            if(node.right != null) queue.offer(node.right);
        }
        list.add(ints);
    }
    return list;
}
</code></pre>
  <h1 data-lake-id="K6e8j" id="K6e8j"><span data-lake-id="ud3f1aba0" id="ud3f1aba0">知识扩展</span></h1>
  <h2 data-lake-id="y42LQ" id="y42LQ"><span data-lake-id="uc4f53f48" id="uc4f53f48">什么是深度优先和广度优先？</span></h2>
  <ol list="ud979aca4">
   <li fid="uded8b9bc" data-lake-id="u65db7882" id="u65db7882"><span data-lake-id="u5f80f5e4" id="u5f80f5e4">深度优先也叫dfs，是指遍历的时候一直按照某个方向遍历，直到该方向遍历完全后，回退到上个节点，再沿着另外的方向遍历，直到所有节点遍历完全。树的前，中，后序遍历就属于dfs。从上面的算法我们可以看出，dfs的遍历在于递归，一般通过栈完成。</span></li>
   <li fid="uded8b9bc" data-lake-id="ud4dc3a16" id="ud4dc3a16"><span data-lake-id="u6182e0fb" id="u6182e0fb">广度优先也叫bfs，是指遍历的时候，直到把根节点周边的节点遍历完后。再把周边节点的每一层遍历，以此类推，直到遍历完成。树的层次遍历就属于bfs。从层次遍历中可以发现，我们一般通过队列完成。</span></li>
  </ol>
  <p data-lake-id="u8f93c379" id="u8f93c379"><span data-lake-id="u6e003166" id="u6e003166">注意，dfs和bfs不止会限于树，图的遍历也可以通过bfs或者dfs完成。</span></p>
  <h2 data-lake-id="utGGu" id="utGGu"><span data-lake-id="uf5620cb9" id="uf5620cb9">相关算法</span></h2>
  <ol list="u412d96e4">
   <li fid="ub67789ba" data-lake-id="u7c765073" id="u7c765073"><span data-lake-id="u4d4da52e" id="u4d4da52e">重建二叉树：</span><a href="https://leetcode.cn/problems/zhong-jian-er-cha-shu-lcof/" target="_blank" data-lake-id="u8c7b2531" id="u8c7b2531"><span data-lake-id="ua6008789" id="ua6008789">https://leetcode.cn/problems/zhong-jian-er-cha-shu-lcof/</span></a></li>
  </ol>
 </body>
</html>